#define _CRT_SECURE_NO_WARNINGS 1
/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;

    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (head == nullptr)return nullptr;

        Node* cur = head;
        Node* newlist = new Node(-1);
        Node* newcur = newlist;
        while (cur) {
            Node* temp = new Node(cur->val);
            temp->random = cur->random;
            Node* t = cur->next;
            cur->next = temp;
            temp->next = t;
            cur = t;
        }
        newcur = head->next;
        newlist->next = newcur;
        cur = head;
        while (newcur) {
            Node* t = nullptr;
            if (newcur->next)t = newcur->next->next;
            if (newcur->random)newcur->random = newcur->random->next;
            else newcur->random = nullptr;
            newcur = t;
        }
        newcur = newlist->next;
        cur = head;
        while (cur && newcur) {
            Node* t = nullptr;
            t = newcur->next;
            cur->next = t;
            cur = cur->next;
            if (t) {
                newcur->next = t->next;
                newcur = newcur->next;
            }
        }

        return newlist->next;
    }
};